﻿#region Copyright (c) 2003 - 2008, Andreas Mueller
/////////////////////////////////////////////////////////////////////////////////////////
// 
// Copyright (c) 2003 - 2008, Andreas Mueller.
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
// Contributors:
//    Andreas Mueller - initial API and implementation
//
// 
// This software is derived from software bearing the following
// restrictions:
// 
// Copyright (c) 1994
// Hewlett-Packard Company
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// Copyright (c) 1996,1997
// Silicon Graphics Computer Systems, Inc.
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// (C) Copyright Nicolai M. Josuttis 1999.
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
// 
/////////////////////////////////////////////////////////////////////////////////////////
#endregion




using NUnit.Framework;
using NStl.Collections;
using System.Collections;
using NUnit.Framework.SyntaxHelpers;
using System.Collections.Generic;
using NStl.SyntaxHelper;
namespace NStl.NUnit.ContainerFixture.PriorityQueue
{
    [TestFixture]
    public class PriorityQueueFixture
    {
        [Test]
        public void Enqueue()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            q.Enqueue(42);
            Assert.AreEqual(42, q.Peek);

            q.Enqueue(84);
            Assert.AreEqual(84, q.Peek);
            Assert.AreEqual(2, q.Count);

            q.Enqueue(50);
            Assert.AreEqual(84, q.Peek);
            Assert.AreEqual(3, q.Count);
        }
        [Test]
        public void IsEmpty()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            Assert.IsTrue(q.Empty);

            q.Enqueue(42);
            Assert.IsFalse(q.Empty);
        }

        [Test]
        public void Dequeue()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            q.Enqueue(42);
            q.Enqueue(84);
            Assert.AreEqual(84, q.Peek);
            Assert.AreEqual(2, q.Count);

            Assert.AreEqual(84, q.Dequeue());
        }
        [Test]
        public void Peek()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            q.Enqueue(42);
            q.Enqueue(84);

            Assert.AreEqual(2, q.Count);
            Assert.AreEqual(84, q.Peek);
            Assert.AreEqual(2, q.Count);
        }

        [Test]
        public void Clear()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            q.Enqueue(42);
            q.Enqueue(84);
            Assert.AreEqual(2, q.Count);
            Assert.IsFalse(q.Empty);

            q.Clear();
            Assert.AreEqual(0, q.Count);
            Assert.IsTrue(q.Empty);
        }
        [Test]
        public void Contains()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            q.Enqueue(42);
            q.Enqueue(84);

            Assert.IsTrue(q.Contains(42));
        }
        [Test]
        public void ContainsFails()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());
            q.Enqueue(42);
            q.Enqueue(84);

            Assert.IsFalse(q.Contains(0));
        }
        [Test]
        public void ToArray()
        {
            int[] expected = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>(), expected);

            Assert.That(q.ToArray(), Is.EquivalentTo(expected));
        }
        [Test]
        public void CtorWithIEnumerableT()
        {
            int[]expected = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>(), (IEnumerable<int>)expected);
            Assert.AreEqual(10, q.Count);
            Assert.That(q, Is.EquivalentTo(expected));
        }
        [Test]
        public void CtorWithParamsArrayT()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>(), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
            Assert.AreEqual(10, q.Count);
            ICollection expected = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Assert.That(q, Is.EquivalentTo(expected));
        }
        [Test]
        public void Piority()
        {
            Vector<int> input = new Vector<int>();
            
            int count = 10;
            for (int i = 0; i < count; ++i)
                input.PushBack(i);

            Algorithm.RandomShuffle(input.Begin(), input.End());


            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>());

            foreach (int i in input)
                q.Enqueue(i);

            for (int i = count - 1; i >= 0; --i)
                Assert.That(i, Is.EqualTo(q.Dequeue()));
        }

        [Test]
        public void Remove()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>(), 0, 1, 2, 3, 4, 5, 5, 6);

            Assert.IsTrue(q.Remove(2));

            Assert.IsFalse(q.Contains(2));

            Vector<int> potentialHeap = new Vector<int>(q);
            Assert.IsTrue(Algorithm.IsHeap(potentialHeap.Begin(), potentialHeap.End()));
        }

        [Test]
        public void RemovePriorityElement()
        {
            PriorityQueue<int> q = new PriorityQueue<int>(Compare.Less<int>(), 0, 1, 2, 3, 4, 5, 5, 6);

            Assert.IsTrue(q.Remove(6));

            Assert.IsFalse(q.Contains(6));

            Vector<int> potentialHeap = new Vector<int>(q);
            Assert.IsTrue(Algorithm.IsHeap(potentialHeap.Begin(), potentialHeap.End()));
        }
    }

}
